//
// Created by Senhai Xu on 2024/7/4.
//
//
// Created by Senhai Xu on 2024/7/4.
//
/**题目： 重建二叉树（只有前中 中后可以重建）
 *给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
 * */

/**思路
 *前序遍历 为根 左子树 右子树
 *中序遍历 为 左子树 根 右子树
 *因此 可以先在 前序遍历 找到根节点，然后在 中序遍历 中通过根节点确定左右子树
 *然后 拿到左子树的前序遍历结果[1，中序根节点索引位+1) 和中序遍历结果[0,中序根节点索引位)
 *递归 得到左子树结构
 *右子树同理
 * */

#include <iostream>
#include<vector>
#include<queue>
#include <algorithm>

using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
//     构造函数（非默认）
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型vector
     * @param vinOrder int整型vector
     * @return TreeNode类
     */
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        if(preOrder.size()!=vinOrder.size()||preOrder.size()<1)
            return nullptr;

        if(preOrder.size()==1)
            return new TreeNode(preOrder[0]);
        //根据中序遍历结果找到根节点索引
        int rootIndex=-1;
        rootIndex = find(vinOrder.begin(),vinOrder.end(),preOrder[0])-vinOrder.begin();
        //没找到 i=-1
        if(rootIndex==-1)
            return nullptr;
        //找到根节点
        TreeNode* root = new TreeNode(preOrder[0]);
        //根据根节点索引确定左子树的前序遍历结果和中序遍历结果
        vector<int> leftPreOrder(preOrder.begin()+1,preOrder.begin()+1+rootIndex);
        vector<int> leftVinOrder(vinOrder.begin(),vinOrder.begin()+rootIndex);
        //递归得到左子树
        root->left = reConstructBinaryTree(leftPreOrder,leftVinOrder);
        //根据根节点索引确定右子树的前序遍历结果和中序遍历结果
        vector<int> rightPreOrder(preOrder.begin()+1+rootIndex,preOrder.end());
        vector<int> rightVinOrder(vinOrder.begin()+1+rootIndex,vinOrder.end());
        //递归得到右子树
        root->right = reConstructBinaryTree(rightPreOrder,rightVinOrder);

        return root;
    }
};
//层序遍历输出树的节点结构
void printTree(TreeNode* root){
    if(root==nullptr)
        return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();
        cout<<node->val<<" ";
        if(node->left!=nullptr)
            q.push(node->left);
        if(node->right!=nullptr)
            q.push(node->right);
    }
}


int main() {
    vector<int>  preOrder= {1,2,4,7,3,5,6,8};
    vector<int>  vinOrder= {4,7,2,1,5,3,8,6};
    Solution solution;
    TreeNode*  root = solution.reConstructBinaryTree(preOrder,vinOrder);
    printTree(root);
    return 0;
}
